package leetcode004;

import com.alibaba.fastjson2.JSON;

/**
 * https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 *
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 */
public class Study004 {


    /**
     * 时间复杂度O(log(m+n))用二分法实现。将问题理解为求第N小的数字
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int k1 = (len1 + len2 + 1) / 2;
        int k2 = (len1 + len2 + 2) / 2;
        int left = findK(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k1);
        int right = findK(nums1, 0, len1 - 1, nums2, 0, len2 - 1, k2);
        return (left + right) / 2.0;
    }

    public int findK(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k){

        //n-1 到 0，len=n，所以要+1
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //保证每次都是nums1先用完
        if (len1 > len2){
            return findK(nums2, start2, end2, nums1, start1, len1, k);
        }
        //nums1用完了
        if (len1 == 0){
            return nums2[start2 + k - 1];
        } else if (k == 1) {
            return Math.min(nums1[start1], nums2[start2]);
        } else {
            int c = k/ 2;
            int index1 = Math.min(start1 + c - 1, nums1.length - 1);
            int index2 = Math.min(start2 + c - 1, nums2.length - 1);
            int num1 = nums1[index1];
            int num2 = nums2[index2];
            if (num1 > num2){
                return findK(nums1, start1, end1, nums2, index2 + 1, end2, k - Math.min(nums2.length, c));
            } else {
                return findK(nums1, index1 + 1, end1, nums2, start2, end2, k - Math.min(nums1.length, c));
            }
        }
    }


    public static void main(String[] args) {
        Study004 study004 = new Study004();
        int[] nums1 = {1,3};
        int[] nums2 = {2};
        double result = study004.findMedianSortedArrays(nums1, nums2);
        System.out.println(JSON.toJSONString(nums1) + ";" + JSON.toJSONString(nums2) + "; result:" + result + "," + (result == 2) );

        nums1 = new int[]{1, 3};
        nums2 = new int[]{2, 4};
        result = study004.findMedianSortedArrays(nums1, nums2);
        System.out.println(JSON.toJSONString(nums1) + ";" + JSON.toJSONString(nums2) + "; result:" + result + "," + (result == 2.5) );

        nums1 = new int[]{2};
        nums2 = new int[]{};
        result = study004.findMedianSortedArrays(nums1, nums2);
        System.out.println(JSON.toJSONString(nums1) + ";" + JSON.toJSONString(nums2) + "; result:" + result + "," + (result == 2.0) );

        nums1 = new int[]{1,2,3};
        nums2 = new int[]{4};
        result = study004.findMedianSortedArrays(nums1, nums2);
        System.out.println(JSON.toJSONString(nums1) + ";" + JSON.toJSONString(nums2) + "; result:" + result + "," + (result == 2.5) );


        nums1 = new int[]{1};
        nums2 = new int[]{2,3,4,5,6};
        result = study004.findMedianSortedArrays(nums1, nums2);
        System.out.println(JSON.toJSONString(nums1) + ";" + JSON.toJSONString(nums2) + "; result:" + result + "," + (result == 3.5) );

        nums1 = new int[]{1,3,4,7,8,9,11};
        nums2 = new int[]{2,3,5,6,7};
        result = study004.findMedianSortedArrays(nums1, nums2);
        System.out.println(JSON.toJSONString(nums1) + ";" + JSON.toJSONString(nums2) + "; result:" + result + "," + (result == 5.5) );
    }
}
